package com.xujiaxin.programme_platform.algorithm;


import java.util.*;

/*
 * 算法题练习
 * */
public class Exercises {

    public static void main(String[] args) {
        Exercises e = new Exercises();
        Ring ring = new Ring();
        HashSet nodes = new HashSet<>();
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        nodes.add(A);
        nodes.add(B);
        nodes.add(C);
        nodes.add(D);
        nodes.add(E);
        ring.nodes = nodes;
        ArrayList<Link> links = new ArrayList<>();
        Link ab = new Link(A, B);
        Link ac = new Link(A, C);
        Link ad = new Link(A, D);
        Link bc = new Link(B, C);
        Link bd = new Link(B, D);
        Link be = new Link(B, E);
        Link de = new Link(D, E);
        links.add(ab);
        links.add(ac);
        links.add(ad);
        links.add(bc);
        links.add(bd);
        links.add(be);
        links.add(de);
        ring.links = links;
        e.computeFarthestRoute(ring, A, B);

    }


    /*
     * 环形结构,查找A节点到B节点最远线路
     *
     * 每到一个节点就copy出一个路线list
     * 通过路线list去记录节点的路线
     * 通过传递唯一容器list去存储的路线list
     * */
    public <T> void computeFarthestRoute(Ring<T> ring, Node<T> start, Node<T> end) {
        List<Node<T>> path = new ArrayList<>();
        List<List<Node<T>>> paths = new ArrayList<>();
        path.add(start);

        extracted(ring, start, path, paths);

        Set<List<Node<T>>> result = null;
        List<Node<T>> tmp = null;
        for (List<Node<T>> list : paths) {
            if (list.get(list.size() - 1).equals(end)) {
                if (result == null && tmp == null) {
                    result = new HashSet<>();
                    result.add(list);
                    tmp = list;
                } else if (tmp.size() < list.size()) {
                    Iterator<List<Node<T>>> it = result.iterator();
                    while (it.hasNext()) {
                        List<Node<T>> next = it.next();
                        if (next.size() < list.size()){
                            it.remove();
                        }
                    }
                    result.add(list);
                    tmp = list;
                } else if (tmp.size() == list.size()) {
                    result.add(list);
                }
            }
        }
        for (List<Node<T>> nodes : result) {
            for (int i = 0; i < nodes.size(); i++) {
                System.out.print(nodes.get(i).name);
                if (i != nodes.size() - 1) {
                    System.out.print(" -> ");
                }
            }
            System.out.println();
        }
    }

    private <T> void extracted(Ring<T> ring, Node<T> start, List<Node<T>> path, List<List<Node<T>>> paths) {
        for (int i = 0; i < ring.links.size(); i++) {
            Link<T> link = ring.links.get(i);
            if (link.startContrast(start.name)) {
                if (path.contains(ring.getLinkEndNode(link))) {//为了确保每个线路的节点不重复
                    paths.add(path);
                    continue;
                }
                List<Node<T>> copy = new ArrayList<Node<T>>(path.size());
                for (Node<T> node : path) {
                    copy.add(node);
                }
                //每次向下传递的线路都要copy一份,然后才加下一个节点.
                // 因为每个节点有多个下节点,所以需要每个路线都是copy
                copy.add(ring.getLinkEndNode(link));
                extracted(ring, ring.getLinkEndNode(link), copy, paths);
            } else if (link.endContrast(start.name)) {
                if (path.contains(ring.getLinkStartNode(link))) {
                    paths.add(path);
                    continue;
                }
                List<Node<T>> copy = new ArrayList<Node<T>>(path.size());
                for (Node<T> node : path) {
                    copy.add(node);
                }
                copy.add(ring.getLinkStartNode(link));
                extracted(ring, ring.getLinkStartNode(link), copy, paths);
            }
        }
    }

}

/*
 * 环里面有多个节点、连线
 * */
class Ring<T> {//环
    public Set<Node<T>> nodes;
    public List<Link<T>> links;

    public void addNode(Node<T> node) {
        if (this.nodes == null) {
            this.nodes = new HashSet<>();
        }
        nodes.add(node);
    }

    public void removeNode(Node<T> node) {
        if (this.nodes == null) {
            return;
        }
        this.nodes.remove(node);
        if (this.links == null) {//有节点不一定有连线,没有节点一定没有连线,两者的关系不是能是并行的
            return;
        }
        Iterator<Link<T>> it = this.links.iterator();
        while (it.hasNext()) {
            Link<T> link = it.next();
            if (link.startContrast(node.name)
                    || link.endContrast(node.name)) {
                it.remove();
            }
        }
    }

    public void addLink(Node start, Node end) {
        if (this.links == null) {
            this.links = new ArrayList<>();
        }
        Link addLink = new Link(start, end);
        for (Link link : this.links) {
            if (link.linkContrast(addLink)) {
                throw new RuntimeException("已经存在相关连接！");
            }
        }
        this.links.add(addLink);
    }

    public void removeLink(Node start, Node end) {
        if (this.links == null) {
            return;
        }
        Link rmLink = new Link(start, end);
        Iterator<Link<T>> it = this.links.iterator();
        while (it.hasNext()) {
            Link<T> link = it.next();
            if (link.linkContrast(rmLink)) {
                it.remove();
            }
        }
    }

    public Node<T> getLinkStartNode(Link<T> link) {
        for (Node<T> node : this.nodes) {
            if (node.name.equals(link.start)) {
                return node;
            }
        }
        return null;
    }

    public Node<T> getLinkEndNode(Link<T> link) {
        for (Node<T> node : this.nodes) {
            if (node.name.equals(link.end)) {
                return node;
            }
        }
        return null;
    }
}

class Node<T> {//网络节点
    public T name;//唯一标识

    public Node(T name) {
        this.name = name;
    }

}

class Link<T> {
    public T start;
    public T end;


    public Link(Node<T> start, Node<T> end) {
        if (start.name.equals(end.name)) {
            throw new RuntimeException("开始节点不能与结束节点相同！");
        }
        this.start = start.name;
        this.end = end.name;
    }

    public boolean linkContrast(Link link) {
        return this.start.equals(link.start) && this.end.equals(link.end);
    }

    public boolean startContrast(T start) {
        return this.start.equals(start);
    }

    public boolean endContrast(T end) {
        return this.end.equals(end);
    }
}